#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>

typedef struct PolyNode *Polynomial;
struct PolyNode{
    int coef;
    int expon;
    Polynomial link;
};

// 函数声明
Polynomial ReadPoly();
void Attach(int c, int e, Polynomial *pRear);
Polynomial Add(Polynomial P1, Polynomial P2);
Polynomial Mult(Polynomial P1, Polynomial P2);
void PrintPoly(Polynomial P);

// 附加新节点
void Attach(int c, int e, Polynomial *pRear){
    Polynomial P = (Polynomial)malloc(sizeof (struct PolyNode));
    P->coef = c;
    P->expon = e;
    P->link = NULL;
    (*pRear)->link = P;
    *pRear = P;
}

// 读取多项式
Polynomial ReadPoly() {
    Polynomial P, Rear, t;
    int c, e, N;
    scanf("%d", &N); // 读取项数
    P = (Polynomial)malloc(sizeof(struct PolyNode));
    P->link = NULL;
    Rear = P; // Rear指向尾部
    while (N--) {
        scanf("%d %d", &c, &e); // 读取系数和指数
        Attach(c, e, &Rear);
    }
    t = P;
    P = P->link; // 返回第一个有效节点
    free(t); // 释放头节点
    return P;
}

// 多项式相乘
Polynomial Mult(Polynomial P1, Polynomial P2) {
    Polynomial P,Rear,t1,t2,t;
    int c,e;
    if(!P1 || !P2) return NULL;
    t1 = P1;t2 = P2;
    P = (Polynomial)malloc(sizeof(struct PolyNode));
    P->link = NULL;
    Rear = P;
    while(t2){
        e = t1->expon + t2->expon;
        c = t1->coef * t2->coef;
        Attach(c, e, &Rear);
        t2 = t2->link;
    }
    t1 = t1->link;
    while (t1){
        t2 = P2;
        Rear = P;
        while (t2){
            e = t1->expon + t2->expon;
            c = t1->coef * t2->coef;
            while(Rear->link&&Rear->link->expon>e){//找插入位置
                Rear = Rear->link;
            }
            if (Rear->link&&Rear->link->expon==e){
                if (Rear->link->coef+c) //判系数是否为0
                {
                    Rear->link->coef += c;
                }
                else  //为0删除节点
                {
                    t = Rear->link;
                    Rear->link = t->link;
                    free(t);
                }
            }
            else  //插入位置
            {
                t = (Polynomial)malloc(sizeof(struct PolyNode));
                t->coef = c;
                t->expon = e;
                t->link = Rear->link;
                Rear->link = t;

                Rear = Rear->link;
            }
            t2 = t2->link;
        }
        t1 = t1->link;
    }
    t = P;
    P = P->link;
    free(t);
    return P;
}

// 多项式相加
Polynomial Add(Polynomial P1, Polynomial P2) {
    Polynomial P, Rear, t1, t2, t3;
    // 初始化指针
    t1 = P1;
    t2 = P2;
    // 创建结果多项式的头节点
    P = (Polynomial)malloc(sizeof(struct PolyNode));
    P->link = NULL;
    Rear = P; // 尾指针初始化为头节点
    // 遍历两个多项式的项
    while (t1 && t2) {
        // 如果指数相等，合并系数
        if (t1->expon == t2->expon) {
            if (t1->coef + t2->coef != 0) { // 如果系数不抵消
                Attach(t1->coef + t2->coef, t1->expon, &Rear); // 添加新项
            }
            t1 = t1->link; // 移动到下一个项
            t2 = t2->link;
        } else if (t1->expon > t2->expon) {
            // t1 的项指数更大，直接添加
            Attach(t1->coef, t1->expon, &Rear);
            t1 = t1->link; // 移动到下一个项
        } else {
            // t2 的项指数更大，直接添加
            Attach(t2->coef, t2->expon, &Rear);
            t2 = t2->link; // 移动到下一个项
        }
    }

    // 将剩余的项添加到结果中
    while (t1) {
        Attach(t1->coef, t1->expon, &Rear);
        t1 = t1->link; // 移动到下一个项
    }
    while (t2) {
        Attach(t2->coef, t2->expon, &Rear);
        t2 = t2->link; // 移动到下一个项
    }

    // 处理头节点并返回结果
    t3 = P; // 暂存头节点
    P = t3->link; // 跳过头节点
    free(t3); // 释放头节点
    return P; // 返回结果多项式
}


// 打印多项式
void PrintPoly(Polynomial P) {
    if (!P) {
        printf("0 0\n");
        return;
    }
    while (P) {
        printf("%d %d%s", P->coef, P->expon,P->link==NULL?"":" ");
        P = P->link;
    }
    printf("\n");
}

int main() {
    Polynomial P1, P2, PP, PS;
    P1 = ReadPoly(); // 读取第一个多项式
    P2 = ReadPoly(); // 读取第二个多项式
    PP = Mult(P1, P2); // 乘法运算
    PrintPoly(PP); // 打印乘法结果
    PS = Add(P1, P2); // 加法运算
    PrintPoly(PS); // 打印加法结果
    return 0;
}